package swordoffer.offer40;

public class Debug {
    public int[] getLeastNumbers(int[] input, int k) {
        int[] res = new int[k];
        int len = input.length;
        if(k == 0 || k > len){
            return res;
        }
        buildMaxHeap(input, k);
        for(int i = k; i < len; i++){
            if(input[i] < input[0]){
                swap(input, 0, i);
                downAdjust(input, 0, k);
            }
        }
        for(int i = 0; i < k; i++){
            res[i] = input[i];
        }
        return res;
    }
    public void buildMaxHeap(int[] arr, int k){
        int len = arr.length;
        for(int i = k / 2 - 1; i >=0; i--){
            downAdjust(arr, i, k);
        }
    }
    public void downAdjust(int[] arr, int p, int heapSize){
        int c = p * 2 + 1;
        while(c < heapSize){
            if(c + 1 < heapSize && arr[c + 1] > arr[c]){
                c++;
            }
            if(arr[p] > arr[c]){
                break;
            }
            swap(arr, p, c);
            p = c;
            c = p * 2 + 1;
        }
    }
    public void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        Debug debug = new Debug();
        int[] arr = new int[]{0,0,1,2,4,2,2,3,1,4};
        int[] numbers = debug.getLeastNumbers(arr, 8);
        for (int number : numbers) {
            System.out.println(number);
        }
    }
}
